package vn.edu.hut.soict.translate.search;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;

import vn.edu.hut.soict.translate.wordgraph.Word;
import vn.edu.hut.soict.translate.wordgraph.WordGraph;

public class SentenceSearcher {
	private static double THRESHOLD;
	private WordGraph wordGraph;
	private PriorityQueue<SearchState> open;
	private HashSet<SearchState> closed;
	private List<SearchState> solutions;
	double upperCost;

	public SentenceSearcher() {
		THRESHOLD = ((double) 1) / 3;
		upperCost = Double.MAX_VALUE;
	}

	public SentenceSearcher(double threshold) {
		THRESHOLD = threshold;
		upperCost = Double.MAX_VALUE;
	}

	public List<SearchState> getSolutions() {
		return solutions;
	}

	private void init(Word[] sentence) {
		SearchState initialState = new SearchState(wordGraph.getStartState(), sentence);
		open.add(initialState);
	}

	private void search(WordGraph wordGraph, Word[] sentence) {
		this.wordGraph = wordGraph;
		open = new PriorityQueue<SearchState>();
		closed = new HashSet<SearchState>();
		solutions = new ArrayList<SearchState>();

		if (upperCost == Double.MAX_VALUE) {
			upperCost = THRESHOLD * (sentence.length + wordGraph.getContentWordCount() + wordGraph.getFunctionWordCount());
		}

		boolean stop = false;

		init(sentence);
		while (true) {
			// Terminate unless OPEN has a state of cost within the cost upper
			// limit.
			stop = true;
			for (SearchState state : open) {
				if (state.getCost() <= upperCost) {
					stop = false;
					break;
				}
			}
			if (stop) {
				break;
			}

			// Remove a state s of least value of f* from OPEN and put s into
			// CLOSED.
			SearchState s = open.remove();
			closed.add(s);

			// If s is a goal state, keep s as a solution.
			// Update the upper limit cost.
			if (s.isGoalState()) {
				upperCost = s.getCost();
				solutions.add(s);
				continue;
			}

			// Threshold
			s.removeInsufficientPath(THRESHOLD);
			if (s.getPaths().size() == 0) {
				continue;
			}

			// Expand s into all of its successors.
			List<SearchState> successors = s.getSuccessors();
			for (SearchState successor : successors) {
				if (successor.getEvaluateCost() <= upperCost) {
					if (!open.contains(successor) && !closed.contains(successor)) {
						open.add(successor);
					}
					else if (open.contains(successor)) {
						SearchState oldState = getSameState(open, successor);
						if (oldState.getCost() > successor.getCost()) {
							open.remove(oldState);
							open.add(successor);
						}
						else if (oldState.getCost() == successor.getCost()) {
							oldState.getPaths().addAll(successor.getPaths());
						}
					}
					else if (closed.contains(successor)) {
						closed.remove(successor);
						open.add(successor);
					}
				}
			}
		}
	}

	private SearchState getSameState(Collection<SearchState> c, SearchState s) {
		for (SearchState old : c) {
			if (s.equals(old)) {
				return old;
			}
		}
		return null;
	}

	public List<SearchState> matchingSequences(WordGraph wordGraph, Word[] sentence) {
		search(wordGraph, sentence);
		return solutions;
	}
}